package main

/*
	给定一个排序数组和一个目标值，在数据中找到目标值，并返回其索引。
	如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
	必须使用时间复杂度为O(logn)的算法
*/
func searchInsert(nums []int, target int) int {
	start := 0
	end := len(nums)-1
	for{
		middle := (start+end)>>1
		if start>end {
			break
		}
		if nums[middle]==target{
			//如果找到目标值，则返回下标
			return middle
		}else if nums[middle] > target{
			//target在左侧
			end = middle-1
		}else{
			//target在右侧
			start = middle+1
		}
	}
	//如果没找到，返回将会被按顺序插入的值
	return start
}

func main(){
	nums := []int{1,3,5,6}
	index := searchInsert(nums, 5)
	print(index)
	index = searchInsert(nums, 2)
	print(index)
	index = searchInsert(nums, 7)
	print(index)
	index = searchInsert(nums, 0)
	print(index)
	nums1 := []int{1}
	index = searchInsert(nums1, 0)
	print(index)
}
